﻿using System;
using System.Collections.Generic;

class PrimeFactorization
{
    static void Main(string[] args)
    {
        Console.WriteLine("正整数分解质因数程序");
        Console.WriteLine("====================");

        while (true)
        {
            Console.Write("\n请输入一个正整数（输入0退出）：");
            string input = Console.ReadLine();

            if (int.TryParse(input, out int number))
            {
                if (number == 0)
                {
                    Console.WriteLine("程序结束！");
                    break;
                }
                else if (number < 2)
                {
                    Console.WriteLine("请输入大于1的正整数！");
                    continue;
                }

                string result = Factorize(number);
                Console.WriteLine(result);
            }
            else
            {
                Console.WriteLine("请输入有效的正整数！");
            }
        }
    }

   
    static string Factorize(int number)
    {
        int original = number;
        List<int> factors = new List<int>();

        
        while (number % 2 == 0)
        {
            factors.Add(2);
            number /= 2;
        }

        
        for (int i = 3; i <= Math.Sqrt(number); i += 2)
        {
            while (number % i == 0)
            {
                factors.Add(i);
                number /= i;
            }
        }

       
        if (number > 2)
        {
            factors.Add(number);
        }

        return FormatResult(original, factors);
    }

  
    static string FormatResult(int original, List<int> factors)
    {
        if (factors.Count == 0)
        {
            return $"{original} 是质数，无法分解";
        }

        string expression = $"{original} = ";
        for (int i = 0; i < factors.Count; i++)
        {
            expression += factors[i];
            if (i < factors.Count - 1)
            {
                expression += " * ";
            }
        }

        return expression;
    }
}